#include <stdlib.h>
#include <stdio.h>
#include "heap.h"
#include "tcpprior.h"

struct sHeap
{
	tcpalpha * elems;
	int tamActual;
	int maxTam;
};

/* prototipo funciones auxiliares (¡NO SE EXPORTAN!) */
int
hijo_izq(const int p);

int
hijo_der(const int p);

int
padre(const int h);

Bool
tiene_hijo(const Heap h, const int p);

Bool
tiene_padre(const Heap h, const int q);

int
hijo_menor(const Heap h, const int p);

Heap
subir(Heap h, int q);

Bool
debe_subir(const Heap h, const int q);

Heap
flotar(Heap h, int q);

Heap
hundir(Heap h, int q);

/* FIN PROTOTIPOS FUNCIONES AUXILIARES */

Heap
heap_create(const tcppos max)
{
	Heap h;

	h = (Heap) malloc (sizeof(struct sHeap));
	if (h!=NULL)
	{
		h->elems = (tcpalpha *) calloc (max+1, sizeof(tcpalpha));
		if (h->elems != NULL)
		{
			h->tamActual = 0;
			h->maxTam = max;
		}
		else
		{
			free(h);
			h = NULL;
			perror("No hay memoria para h->elems (heap_create)");
			exit(EXIT_FAILURE);
		}
	}
	else
	{
		perror("No hay memoria para crear nuevo heap (heap_create)");
		exit(EXIT_FAILURE);
	}
return h;
}

Heap
heap_insert(Heap h, const tcpalpha elem)
{
	tcpalpha aux;
	
	if (heap_lleno(h))
		printf("Warn: Heap lleno, no se pueden agregar más elementos (heap_insert)\n");
	else
	{
		aux = tcpalpha_clone(elem);
		h->tamActual += 1;
		h->elems[h->tamActual] = aux;
		h = flotar(h, h->tamActual);
	}
return h;
}

tcpalpha
heap_primero(const Heap h)
{
	tcpalpha ret;
	if (heap_vacio(h))
	{
		perror("No se puede obtener la raiz de un heap vacio (heap_primero)");
		exit(EXIT_FAILURE);
	}
	else
		ret = tcpalpha_clone(h->elems[1]);
return ret;
}

Heap
heap_pop(Heap h)
{
	if(heap_vacio(h))
	{
		perror("No se puede eliminar la razi de un heap vacio (heap_pop)");
		exit(EXIT_FAILURE);
	}
	else
	{
		h->elems[1] = tcpalpha_destroy(h->elems[1]);
		h->elems[1] = h->elems[h->tamActual];
		h->tamActual -= 1;
		h = hundir(h,1);
	}
return h;
}

Bool
heap_vacio(const Heap h)
{
	Bool b;
	b = (h->tamActual == 0);
return b;
}

Bool
heap_lleno(const Heap h)
{
	Bool b;
	b = (h->tamActual == h->maxTam);
return b;
}

tcpalpha
heap_saca(Heap h)
{
	tcpalpha ret;

	if (heap_vacio(h))
	{
		perror("No se puede sacar elementos de un heap_vacio (heap_saca)");
		exit(EXIT_FAILURE);
	}
	else
	{
		ret = tcpalpha_clone(h->elems[h->tamActual]);
		h->elems[h->tamActual] = tcpalpha_destroy(h->elems[h->tamActual]);
		h->tamActual -= 1;
	}
return ret;
}

/* destructor */
Heap
heap_destroy(Heap h)
{
	int i;

	if (h!=NULL)
	{
		if(h->elems != NULL)
		{
			i = 1;
			while (i<=h->tamActual)
			{
				h->elems[i] = tcpalpha_destroy(h->elems[i]);
				i += 1;
			}
			free(h->elems);
			h->elems = NULL;
		}
		free(h);
		h = NULL;
	}
return h;
}

/* CÓDIGO FUNCIONES AUXILIARES */

int
hijo_izq(const int p)
{
	int hi;
	hi = 2*p;
return hi;
}

int
hijo_der(const int p)
{
	int hd;
	hd = 2*p+1;
return hd;
}

int
padre(const int h)
{
	int p;
	p = (int) h/2.0;
return p;
}

Bool
tiene_hijo(const Heap h, const int p)
{
	Bool b;
	b = ((hijo_izq(p) <= h->tamActual) && p>=1);
return b;
}

Bool
tiene_padre(const Heap h, const int q)
{
	Bool b;
	b = (q>1 && (q<=h->tamActual));
return b;
}
	

int
hijo_menor(const Heap h, const int p)
{
	int hm;
	int hd,hi;

	if (tiene_hijo(h,p))
	{
		hd = hijo_der(p);
		hi = hijo_izq(p);
		if (tiene_padre(h,hd) && prior_ord(alpha_prior(h->elems[hd]),alpha_prior(h->elems[hi])))
			hm = hd;
		else
			hm = hi;
	}
	else
	{
		perror("Indexacion inválida (hijo_menor)");
		exit(EXIT_FAILURE);
	}
return hm;
}

Heap
subir(Heap h, int q)
{
	int p;
	tcpalpha aux;
	
	p = padre(q);
	aux = h->elems[p];	
	h->elems[p] = h->elems[q];
	h->elems[q] = aux;
return h;
} 

Bool
debe_subir(const Heap h, const int q)
{
	Bool b;
	int p;

	p = padre(q);
	b = ((q>1) && (prior_ord((alpha_prior(h->elems[q])), (alpha_prior(h->elems[p])))));
return b;
}

Heap
flotar(Heap h, int q)
{
	int p;

	p = q;
	while (tiene_padre(h,p) && debe_subir(h,p))
	{
		h = subir(h,p);
		p = padre(p);
	}
return h;
}
		
Heap
hundir(Heap h, int q)
{
	int p;

	p = q;
	while ((tiene_hijo(h,p)) && (debe_subir(h, hijo_menor(h,p))))
	{
		p = hijo_menor(h,p);
		h = subir(h,p);
	}
return h;
}
